﻿#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

////未优化初始化
//void LTInit(LTNode** pphead)
//{
//	//创建一个新的节点
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//	if (phead == NULL)
//	{
//		perror("malloc:");
//		exit(1);
//	}
//	//把哨兵位的数据初始化为-1(无效数据)，后驱指针指向自己，前驱指针指向自己
//	*pphead = phead;
//	(*pphead)->data = -1;
//	(*pphead)->next = (*pphead)->prev = *pphead;
//}


////尾插数据
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	//增加节点
//	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
//	if (newnode == NULL)
//	{
//		perror("malloc:");
//		exit(1);
//	}
//	newnode->data = x;
//	newnode->next = newnode->prev = newnode;
//
//	//开始尾插节点
//	//链表中只有哨兵位
//	if (phead->next == phead)
//	{
//		//先把新节点安排好
//		newnode->next = phead;
//		newnode->prev = phead;
//		//哨兵位
//		phead->next = newnode;
//		phead->prev = newnode;
//	}
//	else
//	{
//		//先把新节点安排好
//		newnode->next = phead;
//		newnode->prev = phead->prev;
//		//头节点：phead  尾节点：phead->prev   新节点：newnode
//		phead->prev->next = newnode;
//		phead->prev = newnode;
//	}
//}


//增加节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}


////初始化
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}


//初始化
LTNode* LTInit()
{
	LTNode* pplist = LTBuyNode(-1);
	return pplist;
}


//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//开始尾插节点  
	//链表中只有哨兵位
	if (phead->next == phead)
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead;
		//哨兵位
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
		//先把新节点安排好
		newnode->next = phead;
		newnode->prev = phead->prev;
		//头节点：phead  尾节点：phead->prev   新节点：newnode
		phead->prev->next = newnode;
		phead->prev = newnode;
	}
}


//打印数据
void LTPrint(LTNode* phead)
{
	//遍历寻找
	LTNode* pcur = phead->next;//头节点的数据是无效的，因此就不需要打印
	//因为是循环的，所以不能用空指针来判断，要看看是否指向的哨兵位
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}


////尾删数据
//void LTPopBack(LTNode* phead)
//{
//	assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素
//	if (phead->next->next == phead)//只有一个有效数据
//	{
//		LTNode* freenode = phead->next;
//		free(freenode);
//		phead->next = phead;
//		phead->prev = phead;
//	}
//	else
//	{
//		phead->prev->prev->next = phead;
//		LTNode* freenode = phead->prev;
//		phead->prev = phead->prev->prev;
//		free(freenode);
//		freenode = NULL;
//	}
//}


//尾删数据
void LTPopBack(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素
	phead->prev->prev->next = phead;
	LTNode* freenode = phead->prev;
	phead->prev = phead->prev->prev;
	free(freenode);
	freenode = NULL;
}


////头插数据
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	LTNode* newnode = LTBuyNode(x);
//	if (phead->next == phead)//只有哨兵位
//	{
//		newnode->next = phead;
//		newnode->prev = phead;
//		phead->next = newnode;
//		phead->prev = newnode;
//	}
//	else
//	{
//		//先安排新节点
//		newnode->next = phead->next;
//		newnode->prev = phead;
//		//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnode
//		phead->next->prev = newnode;
//		phead->next = newnode;
//	}
//}


//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//先安排新节点
	newnode->next = phead->next;
	newnode->prev = phead;
	//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnode
	phead->next->prev = newnode;
	phead->next = newnode;
}


//头删数据
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空
	phead->next->next->prev = phead;
	LTNode* freenode = phead->next;
	phead->next = phead->next->next;
	free(freenode);
	freenode = NULL;
}


//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//先安排好新节点
	newnode->prev = pos;
	newnode->next = pos->next;
	
	pos->next = newnode;
	pos->next->prev = newnode;
}


//在pos位置删除数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}


//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}


//销毁链表
void LTDestroy(LTNode* phead)
{
	assert(phead);
	//就是节点一个一个的销毁
	LTNode* pcur = phead->next;
	
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(pcur);
	pcur = NULL;
}